#include <bits/stdc++.h>
#include <string>
using namespace std;

/** 二叉搜索树 */
struct BST
{
    int value;         // 节点值
    struct BST *left;  // 左子树
    struct BST *right; // 右子树
};

/** 初始化 */
struct BST *initTree(struct BST *t)
{
    t = NULL;
    return t;
}

/** 插入节点到树 */
struct BST *insertTree(struct BST *t, int val)
{
    if (t == NULL)
    {
        struct BST *node = (struct BST *)malloc(sizeof(struct BST));
        node->value = val;
        node->left = node->right = NULL;
        return node;
    }
    else
    {
        if (val > t->value)
            t->right = insertTree(t->right, val);
        else if (val < t->value)
            t->left = insertTree(t->left, val);
        return t;
    }
}

/** 删除二叉树中的一个节点 */
struct BST *deleteTree(struct BST *tree, int val)
{
    if (tree == NULL)
        return tree;
    if (val > tree->value)
        tree->right = deleteTree(tree->right, val);
    else if (val < tree->value)
        tree->left = deleteTree(tree->left, val);
    else
    {
        if (tree->left && tree->right)
        {
            int minVal = findTreeMin(tree->right);
            tree->value = minVal;
            tree->right = deleteTree(tree->right, minVal);
        }
        else
        {
            struct BST *t = tree;
            if (tree->left)
            {
                tree = tree->left;
            }
            else if (tree->right)
            {
                tree = tree->right;
            }
            free(t);
        }
    }
    return tree;
}

/** 查找树中的最大值 */
int findTreeMax(const struct BST *t)
{
    if (t == NULL)
        return -INT_MAX;
    if (t->right == NULL)
        return t->value;
    return findTreeMax(t->right);
}

/** 求树的高度 */
int findTreeHeight(struct BST *t)
{
    if (t == NULL)
        return 0;
    return max(findTreeHeight(t->left), findTreeHeight(t->right)) + 1;
}

/** 求树的节点个数 */ 
int findTreeSize(struct BST* t)
{
    if(t==NULL) return 0;
    return findTreeSize(t->left) + findTreeSize(t->right) + 1;
}

/** 排序树的节点（中序） */
void sortTree(const struct BST* t){
  if(t==NULL) return;
  sortTree(t->left);
  cout << t->value << " ";
  sortTree(t->right);
}

/** 排序树的节点（前序） */
void fontTree(const struct BST* t){
  if(t==NULL) return;
  cout << t->value << " ";
  sortTree(t->left);
  sortTree(t->right);
}

int main()
{

    struct BST *tree = initTree(tree);
    tree = insertTree(tree, 20);
    tree = insertTree(tree, 50);
    tree = insertTree(tree, 30);
    tree = insertTree(tree, 15);
    tree = insertTree(tree, 10);
    tree = insertTree(tree, 5);
    cout << findTreeMax(tree) << endl;
    cout << findTreeHeight(tree) << endl;
    sortTree(tree);
    return 0;
}